/*
 * Copyright (C) 2008 by The Regents of the University of California
 * Redistribution of this file is permitted under the terms of the GNU
 * Public License (GPL).
 *
 * @author Junghoo "John" Cho <cho AT cs.ucla.edu>
 * @date 3/24/2008
 */

#ifndef BTREEINDEX_H
#define BTREEINDEX_H

#include "Bruinbase.h"
#include "BTreeNode.h"
#include "PageFile.h"
#include "RecordFile.h"
#include <cstring>
#include <stack>

#define RC_ERROR -1338
#define RC_BACKTRACK -1339
#define RC_UNINITIALIZED -1340
#define RC_READONLY -1341

/**
 * The data structure to point to a particular entry at a b+tree leaf node.
 * An IndexCursor consists of pid (PageId of the leaf node) and 
 * eid (the location of the index entry inside the node).
 * IndexCursor is used for index lookup and traversal.
 */
typedef struct {
  // PageId of the index entry
  PageId  pid;  
  // The entry number inside the node
  int     eid;  
} IndexCursor;

class BTPageByteBuffer {
  public:
    BTPageByteBuffer() {
      memset(buffer, 0, sizeof(buffer));
      bufferPointer = 0;
    }
    BTPageByteBuffer(char *existingBuffer) {
      memcpy(buffer, existingBuffer, sizeof(buffer));
      bufferPointer = 0;
    }
    bool appendInt(int integer) {
      if (bufferPointer + sizeof(integer) > sizeof(buffer))
        return false;
      memcpy(buffer + bufferPointer, &integer, sizeof(integer));
      bufferPointer += sizeof(integer);
      return true;
    }
    bool readInt(int& integer) {
      if (bufferPointer + sizeof(integer) > sizeof(buffer))
        return false;
      memcpy(&integer, buffer + bufferPointer, sizeof(integer));
      bufferPointer += sizeof(integer);
      return true;
    }
    const char *rawBuffer() const {
      return buffer;
    }
  private:
    char buffer[PageFile::PAGE_SIZE];
    int bufferPointer;
};

/**
 * Implements a B-Tree index for bruinbase.
 * 
 */
class BTreeIndex {
 public:
  BTreeIndex();

  /**
   * Open the index file in read or write mode.
   * Under 'w' mode, the index file should be created if it does not exist.
   * @param indexname[IN] the name of the index file
   * @param mode[IN] 'r' for read, 'w' for write
   * @return error code. 0 if no error
   */
  RC open(const std::string& indexname, char mode);

  /**
   * Close the index file.
   * @return error code. 0 if no error
   */
  RC close();
    
  /**
   * Insert (key, RecordId) pair to the index.
   * @param key[IN] the key for the value inserted into the index
   * @param rid[IN] the RecordId for the record being inserted into the index
   * @return error code. 0 if no error
   */
  RC insert(int key, const RecordId& rid);

  /**
   * Find the leaf-node index entry whose key value is larger than or
   * equal to searchKey and output its location (i.e., the page id of the node
   * and the entry number in the node) as "IndexCursor."
   * IndexCursor consists of pid (page id of the node that contains the 
   * searchKey) and eid (the entry number inside the node)
   * to indicate the location of a particular index entry in the B+tree.
   * Note that, for range queries, we need to scan the B+tree leaf nodes.
   * For example, if the query is "key > 1000", we should scan the leaf
   * nodes starting with the key value 1000. For this reason,
   * this function returns the location of the leaf node entry
   * for a given searchKey, instead of returning the RecordId
   * associated with the searchKey.
   * Using the returned "IndexCursor", you will have to call readForward()
   * to retrieve the actual (key, rid) pair from the index.
   * @param key[IN] the key to find
   * @param cursor[OUT] the cursor pointing to the first index entry
   * with the key value
   * @return error code. 0 if no error.
   */
  RC locate(int searchKey, IndexCursor& cursor) const;

  /**
   * Read the (key, rid) pair at the location specified by the index cursor,
   * and move foward the cursor to the next entry.
   * @param cursor[IN/OUT] the cursor pointing to an leaf-node index entry in the b+tree
   * @param key[OUT] the key stored at the index cursor location
   * @param rid[OUT] the RecordId stored at the index cursor location
   * @return error code. 0 if no error
   */
  RC readForward(IndexCursor& cursor, int& key, RecordId& rid);

 private:
  PageFile pf;         /// the PageFile used to store the actual b+tree in disk

  PageId   rootPid;    /// the PageId of the root node
  int      treeHeight; /// the height of the tree
  /// Note that the content of the above two variables will be gone when
  /// this class is destructed. Make sure to store the values of the two 
  /// variables in disk, so that they can be reconstructed when the index
  /// is opened again later.

  bool inited;
  bool writable;

  // For caching readForward() reads.
  BTLeafNode leaf;
  PageId leafPid;

  /*
   * Internal helper function for BTreeIndex::_insert_into_leaf().
   * @param pid1[IN] a pointer to all the nodes less than the key
   *                 (used only when need to create new root).
   * @param key[IN] the key to be inserted into the parent.
   * @param pid2[IN] a pointer to all the nodes greater than the key.
   * @param parentPids[IN/OUT] a stack containing the parents of the current
   *                           node, up to the root.
   * @return error code. 0 if no error.
   */
  RC _insert_into_parent(PageId pid1, int key, PageId pid2, std::stack<PageId> &parentPids);

  /*
   * Internal helper function for BTreeIndex::insert().
   * @param key[IN] the key for the value inserted into the index
   * @param rid[IN] the RecordId for the record being inserted into the index
   * @param level[IN] the current level of the tree (0 ... treeHeight - 1) for
   *                  keeping track of recursion.
   * @param pid[IN] the pid of the node at which to start the recursion
   *                (indicates the current node).
   * @param leafIndex[IN] once at the leaf level, this keeps track of which leaf
   *                      node we are at (leftmost leaf node has index 0).
   * @param parentPids[IN/OUT] a stack containing the parents of the current
   *                           node, up to the root.
   * @return error code. 0 if no error.
   */
  RC _insert_into_leaf(int key, const RecordId& rid, int level, PageId pid, int leafIndex, std::stack<PageId> &parentPids);

  /*
   * Internal helper function for BTreeIndex::locate().
   * @param searchKey[IN] the key to find.
   * @param cursor[OUT] the cursor pointing to the first index entry
   *                    with the key value.
   * @param level[IN] the current level of the tree (0 ... treeHeight - 1) for
   *                  keeping track of recursion.
   * @param pid[IN] the pid of the node at which to start the recursion.
   *                (indicates the current node).
   * @return error code. 0 if no error.
   */
  RC _locate(int searchKey, IndexCursor& cursor, int level, PageId pid) const;
};

#endif /* BTREEINDEX_H */
